今天要說的是 B+ Tree，是 B Tree 的變種

何謂 B+ Tree

基本上，B+ Tree 大部分都跟 B Tree 一樣，但有個不同的地方。

B+ Tree 支援 ISAM(Index Sequential Access Method)，因此是許多檔案系統和資料庫使用的儲存方式。
分為 2 個 Level

1. index level：用來查詢 data block
2. Data block level：用來儲存資料的 level，通常位於樹葉節點，且每個節點會用鏈結串起

來看個圖：https://www.geeksforgeeks.org/introduction-of-b-tree/

與 B Tree 的差別

1. 基本上會將與索引相同的資料，放在索引的右邊。也就是小於的資料放索引左邊，大於等於的資料放索引右邊
2. 操作大致與 B Tree 相同，但操作時必須資料歸資料，索引歸索引，不可隨意刪除資料（Rotation, Combine, Split 時）

Insert X into a B+ Tree of order m

我們直接用一個例子來看：

可以看到，因為 5 位於 data block，當 split 到 parent 時，原本 data block 的資料不可以被刪除，要保留，於是在 parent 上 copy 一個 5 上去。但接下來的 17 因為只是索引，因此就按照 B Tree 的操作，直接刪除 split。

delete X in B+ Tree of order m

繼續用剛剛的 Tree 來看：

Combine 和 Rotation 操作都有一點不同，但主要就是要避免** Index 出現在 data Block level**，或是誤刪了 Data Block 中的資料